import copy
from typing import List


#
def solveNQueens(n: int) -> List[List[str]]:
    # 棋盘
    n_n = [['.' for _ in range(n)] for _ in range(n)]

    result_list = list()

    def check_topLeft_topRight(row: int, column: int, chessboard: List[List[str]]) -> bool:
        '''
        检测斜方向上面是否有值
        :param row:
        :param column:
        :param chessboard:
        :return:
        '''
        # 左斜，同一条斜线上面，【行下标-列下标】的值相等
        for i in range(1, row + 1):
            if row - i >= 0 and column - i >= 0 and chessboard[row - i][column - i] == "Q":
                return True

        # 右斜，同一条斜线上面，【行下标+列下表】的值相等
        for i in range(1, row + 1):
            if row - i >= 0 and column + i < len(chessboard) and chessboard[row - i][column + i] == "Q":
                return True

        return False

    def check_left_top(row: int, column: int, chessboard: List[List[str]]) -> bool:
        '''
        检测横-纵方向上面是否有值
        :param row:
        :param column:
        :param chessboard:
        :return:
        '''
        # 纵向找到一个
        for row_i in range(row - 1, -1, -1):
            if chessboard[row_i][column] == "Q":
                return True

        # 横向找到一个
        for column_j in range(column - 1, -1, -1):
            if chessboard[row][column_j] == "Q":
                return True

        return False

    def convert_to_re(re_list: List[List[str]]) -> List[str]:
        str_re = list()
        for str_list in re_list:
            str_re.append(''.join(str_list))
        return str_re

    def back_track(row: int, max_board: int, chessboard: List[List[str]], re_list: List[List[str]]):
        '''
        :param row:
        :param max_board:
        :param chessboard:
        :return:
        '''
        # 小于 max_board 的 row，全部符合条件
        if row == max_board:
            re_list.append(convert_to_re(chessboard))
            return

        temp_re = 0

        for column in range(max_board):
            # 校验当前位置(row,column)在横向，纵向，左斜方向上，右斜方向上是否有冲突
            # True 表示有冲突
            check_conflict = (check_left_top(row, column, chessboard)
                              or check_topLeft_topRight(row, column, chessboard))
            # 有冲突
            if check_conflict:
                continue

            chessboard[row][column] = 'Q'
            row += 1

            back_track(row, n, chessboard, result_list)

            row -= 1
            chessboard[row][column] = '.'

        # 返回累计的结果
        return temp_re

    back_track(0, n, n_n, result_list)

    return result_list


result = solveNQueens(1)
print(f"result:{result}")

result = solveNQueens(2)
print(f"result:{result}")

result = solveNQueens(3)
print(f"result:{result}")

result = solveNQueens(4)
print(f"result:{result}")
